/*
 * @Author: szx
 * @Date: 2021-12-29 13:48:38
 * @LastEditTime: 2021-12-29 14:11:04
 * @Description:
 * @FilePath: \leetcode\300-399\332\332.js
 */
/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {
    let result = ['JFK'];
    let map = {};

    for (const tickt of tickets) {
        const [from, to] = tickt;
        if (!map[from]) {
            map[from] = [];
        }
        map[from].push(to);
    }
    for (const city in map) {
        // 对到达城市列表排序
        map[city].sort();
    }

    const backtracing = () => {
        if (result.length === tickets.length + 1) {
            return true;
        }
        const lastCityTickets = map[result[result.length - 1]];

        if (!lastCityTickets || !lastCityTickets.length) {
            return false;
        }
        for (let i = 0; i < lastCityTickets.length; i++) {
            let city = lastCityTickets[i];
            // 删除已走过航线，防止死循环
            lastCityTickets.splice(i, 1);
            result.push(city);
            if (backtracing()) {
                return true;
            }
            result.pop();
            lastCityTickets.splice(i, 0, city);
        }
    };
    backtracing();
    return result;
};
console.log(
    findItinerary([
        ['JFK', 'SFO'],
        ['JFK', 'ATL'],
        ['SFO', 'ATL'],
        ['ATL', 'JFK'],
        ['ATL', 'SFO']
    ])
);
